<?php
//排序数组
$arr = [];
for ($i = 0; $i < 100; $i++) {
    $arr[] = rand(1, 100);
}

//快速排序
function quickSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $left = $right = [];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $leftArr = quickSort($left);
    $rightArr = quickSort($right);
    return array_merge($leftArr, [$arr[0]], $rightArr);
}

//冒泡排序
function maoPaoSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tem = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tem;
            }
        }
    }
    return $arr;
}

//选择排序
function changeSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        $maxKey = $i;
        for ($j = $i; $j < $length; $j++) {
            if ($arr[$maxKey] > $arr[$j]) {
                $maxKey = $j;
            }
        }
        $tem = $arr[$i];
        $arr[$i] = $arr[$maxKey];
        $arr[$maxKey] = $tem;
    }
    return $arr;
}

//插入排序
function insertSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length; $i++) {
        $key = $i - 1;
        $value = $arr[$i];
        while ($key >= 0 && $arr[$key] > $value) { //只要当前前面的值比当前值大(第一个不用比较)
            $arr[$key + 1] = $arr[$key]; //后移
            $key--;
        }
        //将当前值放到空出来的位置
        $arr[$key + 1] = $value;
    }
    return $arr;
}


$arr = [1, 2, 4, 5, 7, 8, 9, 10, 15, 20];

//二分查找
function halfFind($x, $arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    $min = 0;
    $max = $length - 1;
    while ($min <= $max) {
        $middle = intval(($min + $max) / 2);
        if ($x > $arr[$middle]) {
            $min = $middle + 1;
        } elseif ($x < $arr[$middle]) {
            $max = $middle - 1;
        } else {
            return $middle;
        }
    }
    return false;
}

